import java.util.*;

/**
 * @author hewei
 * @version 1.0
 * @description: 6242. 二叉搜索树最近节点查询
 * @date 2022/11/20 14:22
 */

public class ClosestNodes {

    List<Integer> list;
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        list = new ArrayList<>();
        process(root);
        int m = list.size(), n = queries.size(), p = 0;
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ans.add(new ArrayList<>());
            a.add(i);
        }
        a.sort(Comparator.comparingInt(queries::get));
        for (int i = 0; i < n; i++) {
            while (p < m && list.get(p) < queries.get(a.get(i))) {
                ++p;
            }
            List<Integer> temp = ans.get(a.get(i));
            if (p == m) {
                temp.add(list.get(m - 1));
                temp.add(-1);
            } else if (p > 0) {
                if (list.get(p) > queries.get(a.get(i))) {
                    temp.add(list.get(p - 1));
                } else {
                    temp.add(list.get(p));
                }
                temp.add(list.get(p));
            } else {
                if (!Objects.equals(queries.get(a.get(i)), list.get(p))) {
                    temp.add(-1);
                } else {
                    temp.add(list.get(p));
                }
                temp.add(list.get(p));
            }
        }
        return ans;
    }

    public void process(TreeNode node) {
        if (node == null) return;
        process(node.left);
        list.add(node.val);
        process(node.right);
    }
}
